/*
 * @lc app=leetcode.cn id=30 lang=cpp
 * @lcpr version=30204
 *
 * [30] 串联所有单词的子串
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wordSize = words[0].size(); //单词大小
        int wordNum = words.size();     //单词数量
        vector<int> res;
        for (int i = 0; i < wordSize && i + wordSize * wordNum <= s.size(); ++i) 
        {
            // 滑动窗口 左闭右开
            int left = i;                           //初始化滑动窗口左边界
            int right = i + wordSize * wordNum;     //右边界
            unordered_map<string, int> wordsMap;    //保存当前窗口与words里单词的次数关系
            //初始化滑动窗口内单词计数
            for (int j = left; j < right; j += wordSize)
                wordsMap[s.substr(j, wordSize)]++;
            //减去words里出现的次数
            for (string& word : words) 
            {
                wordsMap[word]--;
                if (wordsMap[word] == 0)
                    wordsMap.erase(word);
            }
            //判断初始状态是否满足
            if (wordsMap.empty())
                res.push_back(left);
            while (right < s.size()) 
            {
                //滑动一次，从左边界开始的一个单词需要删除，右边界开始的单词需要加入
                const string& deleteWord = s.substr(left, wordSize);
                const string& joinWord = s.substr(right, wordSize);
                if (--wordsMap[deleteWord] == 0)
                    wordsMap.erase(deleteWord);
                if (++wordsMap[joinWord] == 0)
                    wordsMap.erase(joinWord);

                //滑动之后更新边界，并判断是否满足
                right += wordSize;
                left += wordSize;
                if (wordsMap.empty())
                    res.push_back(left);
            }
        }
        return res;
    }
};
// @lc code=end



/*
// @lcpr case=start
// "barfoothefoobarman"\n["foo","bar"]\n
// @lcpr case=end

// @lcpr case=start
// "wordgoodgoodgoodbestword"\n["word","good","best","word"]\n
// @lcpr case=end

// @lcpr case=start
// "barfoofoobarthefoobarman"\n["bar","foo","the"]\n
// @lcpr case=end

 */

